//package com.douqu.game.core.util;
//
//import com.douqu.game.core.entity.battle.Grid;
//
//import java.util.List;
//import java.util.Map;
//import java.util.Queue;
//
///**
// * Created by bean on 2017/7/27.
// */
//public class RouteUtils {
//
//    public static boolean dijstra(int[] origin, int[] aim, int[][] visited, int[][] dir1, int[][] dir2, int[][] dir3, int[][] length, Grid[][] map, Map<String, int[][]> searchResult, List<int[][]> searchProcess)
//    {
//
//        for (int i = 0; i < length.length; i++) {
//            for (int j = 0; j < length[0].length; j++) {
//                length[i][j] = 10000;
//            }
//        }
//
//        boolean flag = true;
//        int[] start = { origin[0], origin[1] };
//        visited[origin[1]][origin[0]] = 1;
//
//        for (int[] a : dir1) {
//
//            int row = start[0] + a[0];
//            int col = start[1] + a[1];
//
//            if (row < 0 || row >= map.length || col < 0
//                    || col >= map[0].length)
//                continue;
//            if (!map[row][col].isFree())
//                continue;
//
//            length[row][col] = 2;
//
//            String key = row + ":" + col;
//            int[][] al = new int[][] { { start[0], start[1] },
//                    { row, col } };
//            searchResult.put(key, al);
//
//            searchProcess.add(new int[][] { { start[0], start[1] },
//                    { row, col } });
//
//        }
//
//        for (int[] b : dir2) {
//
//            int row = start[0] + b[0];
//            int col = start[1] + b[1];
//
//            if (row < 0 || row >= map.length || col < 0
//                    || col >= map[0].length)
//                continue;
//            if (map[row][col].isNotFree() || map[row][col - b[1]].isNotFree() || map[row - b[0]][col].isNotFree())
//                continue;
//
//            length[row][col] = 3;
//
//            String key = row + ":" + col;
//            int[][] al = new int[][] { { start[0], start[1] },
//                    { row, col } };
//            searchResult.put(key, al);
//
//            searchProcess.add(new int[][] { { start[0], start[1] },
//                    { row, col } });
//
//        }
//
//
//        loop: while (flag) {
//
//            try {
//                int[] temp = new int[2];
//                boolean is = false;
//                int minLen = 10000;
//                for (int i = 0; i < visited.length; i++) {
//                    for (int j = 0; j < visited[0].length; j++) {
//                        if (visited[i][j] == 0) {
//                            if (minLen > length[i][j]) {
//                                minLen = length[i][j];
//                                temp[0] = i;
//                                temp[1] = j;
//                                is = true;
//                            }
//                        }
//                    }
//                }
//
//                if (map[temp[0]][temp[1]].isNotFree() || is == false) {
//                    System.out.println("找不到路线");
//                    break loop;
//                }
//
//                visited[temp[0]][temp[1]] = 1;
//
//                int length1 = length[temp[0]][temp[1]];
//
//                int index = 0;
//                for (int[] a1 : dir3) {
//
//                    index++;
//                    int row = temp[0] + a1[0];
//                    int col = temp[1] + a1[1];
//
//                    if (row < 0 || row >= map.length || col < 0
//                            || col >= map[0].length)
//                        continue;
//                    if (index <= 4 && map[row][col].isNotFree())
//                        continue;
//                    if (index > 4 && map[row][col].isNotFree()
//                            || map[row][col - a1[1]].isNotFree()
//                            || map[row - a1[0]][col].isNotFree())
//                        continue;
//
//                    int length2 = length[row][col];
//                    int lengthSum = 0;
//                    if (index <= 4) {
//                        lengthSum = length1 + 2;
//                    } else if (index > 4) {
//                        lengthSum = length1 + 3;
//                    }
//
//                    if (length2 > lengthSum) {
//
//                        String key = row + ":" + col;
//                        searchResult.put(key, new int[][] {
//                                { temp[0], temp[1] }, { row, col } });
//
//                        length[row][col] = lengthSum;
//
//                        if (length2 == 10000) {
//
//
//                            searchProcess
//                                    .add(new int[][] {
//                                            { temp[0], temp[1] },
//                                            { row, col } });
//
//                        }
//
//                    }
//
//                    if (row == aim[0] && col == aim[1]) {
//
//                        break loop;
//
//                    }
//                }
//
//            } catch (Exception e) {
////                e.printStackTrace();
////                break loop;
//                return false;
//            }
//        }
//
//        return true;
//
//    }
//
//    public static boolean gdyx(Queue<int[][]> queue, int[] origin, int[] aim, int[][] visited, int[][] dir1, int[][] dir2, Grid[][] map, Map<String, int[][]> searchResult, List<int[][]> searchProcess) {
//
//        boolean flag = true;
//        int[][] start = { { origin[0], origin[1] },
//                { origin[0], origin[1] } };
//        queue.offer(start);
//
//        loop: while (flag) {
//
//            try {
//                int[][] currentEdge = queue.poll();
//
//                int[] tempTarget = currentEdge[1];
//
//                if(visited.length <= tempTarget[1])
//                    continue;
//
//                if (visited[tempTarget[1]][tempTarget[0]] == 1) {
//                    continue;
//                }
//
//                visited[tempTarget[1]][tempTarget[0]] = 1;
//
//                searchProcess.add(currentEdge);
//
//                searchResult.put(tempTarget[0] + ":" + tempTarget[1],
//                        new int[][] { currentEdge[1], currentEdge[0] });
//
//                if (tempTarget[0] == aim[0] && tempTarget[1] == aim[1]) {
//                    break;
//                }
//
//                int currCol = tempTarget[1];
//                int currRow = tempTarget[0];
//
//                for (int[] a : dir1) {
//
//                    int i = a[0];
//                    int j = a[1];
//
//                    if (i == 0 && j == 0) {
//                        continue;
//                    }
//
//                    if (currRow + i >= 0 && currRow + i < map.length
//                            && currCol + j >= 0
//                            && currCol + j < map[0].length
//                            && map[currRow + i][currCol + j].isFree()) {
//
//                        int[][] tempEdge = {
//                                { tempTarget[0], tempTarget[1] },
//                                { currRow + i, currCol + j } };
//
//                        queue.offer(tempEdge);
//
//                    }
//                }
//
//                for (int[] b : dir2) {
//
//                    int i = b[0];
//                    int j = b[1];
//
//                    if (i == 0 && j == 0) {
//                        continue;
//                    }
//                    if (currRow + i >= 0 && currRow + i < map.length
//                            && currCol + j >= 0
//                            && currCol + j < map[0].length
//                            && map[currRow + i][currCol + j].isFree()
//                            && map[currRow][currCol + j].isFree()
//                            && map[currRow + i][currCol].isFree()) {
//
//                        int[][] tempEdge = {
//                                { tempTarget[0], tempTarget[1] },
//                                { currRow + i, currCol + j } };
//
//                        queue.offer(tempEdge);
//
//                    }
//                }
//
//            } catch (Exception e) {
//                System.out.println("找不到路线");
//                return false;
//            }
//
//        }
//        return true;
//
//    }
//}
